학교때 열씸히 배웠던것을 잊어버리기 아깝고 처음 공부하는 분이라면
도움도 드릴 수 있지 않을까 해서 꾸준히 올리려 했으나 짬내기가 쉽지 않네요.
암튼 열씨미 합시다. ^^

문자열 패턴 매칭은 입력으로서 텍스트 T 와 패턴 P 가 주어진다.

둘은 문자열이며, 프로그램상에서는 문자의 배열로 표현될 수 있다.
하고싶은  일은, 텍스트에서 패턴이 나타나는 모든 위치를 찾아내는 것이다.
예를들어 텍스트 abababc이고 패턴이 aba라면 답은 첫번재와, 세번째 위치이다.

간단히 생각할 수 있는 알고리즘이라면 다음과 같습니다.
텍스트의 길이는 n으로 표시하며 패턴의 길이는 m으로 표시한다.
for( i = 0 ; i < 텍스트 상의 마지막 위치 ; i++)
{
    j=i, k=패턴의처음위치;
    while(텍스트의 j번째 글자와 패턴의 k번째 글자가 같은 동안)
    {
        j++, k++;
    }
    if(패턴의 끝을 지났으면 ) 발견;
    else 미발견;
}
이 알고리즘의 시간복잡도는 바깥쪽 루프는 최대 n번 반복된다.
안쪽 루프는 최대 m 번 반복될 수 있다. 따라서, 시간복잡도는 O(mn)이다.
실제로 이렇게 걸리는 예는 aaaaaaaaaaaaaaa에서 aaab 찾기

물론 최악의 알고리즘 중에 하나입니다.
백만줄짜리 패턴을 1조개의 문자열에서 찾는다면 (1조 * 백만) 입니다.
게놈프로젝트 같은데서 이런 알고리즘을 사용한다면 아마 지구종말까지 해야 하겠죠.
그러나, 문자열 패턴매칭분야에선 이미 최적의 알고리즘이 나와있습니다.


KMP알고리즘 (크누스-모리스-프라트 알고리즘)
알고리즘을 개발한 Kunth, Morris, Pratt 세분의 이름 머리글자를 따서 KMP입니다.

이상적인 알고리즘은 O(m+n) 시간에 동작하는 것인데 패턴과 문자열을 최소한 1번은 읽어야
비교할 수 있지 않겠습니까 ^^
자~ 이런 놀라운 알고리즘이 이미 만들어져 있고 여러분은 배워서 쓰기만 하면 됩니다.

입력 T :            a b c a b c a b c d a b d a b b a
패턴 P :            a b c a b c d
답을 찾은 경우            a b c a b c d

화살표는 알고리즘을 사용하는 "설명서"에 해당하는데 패턴을 이용해 생성된다.
알고리즘은 왼쪽의 시작 동그라미에서 시작한다.
알고리즘은 텍스트의 하나의 글자를 읽을 때마다 현재의 동그라미에서 그 글자가 붙어 있는 줄을 따라서 다음의 동그라미로 이동한다.

알고리즘을 시연해 보면 d를 읽은 직후 끝에 들어감을 알 수 있다.
"끝" 동그라미에 들어가면 일치하는 패턴을 찾은 것이다.
이 알고리즘을 구현하기 위해서는 설명서를 만들고 표현하는 방법이 있어야 하지만 중요한 것은 이전 알고리즘과의 관계이다.

화살표를 따라 움직이는 과정은 이전 알고리즘과 대비할 수 있는데,
오른쪽 화살표를 따르는 과정은 이전 알고리즘의 안쪽 루프에서 한단계 진행하는 것과 동일하다.
왼쪽 화살표를 따르는 것은 이전 알고리즘의 바깥쪽 루프 여러개와 안쪽 루프 여러개를 건너뛰는 것에 해당한다.

예를들어 텍스트의 abcabca까지 읽은 상태를 보도록 하자,
이때 왼쪽 화살표를 따라서 이동하게 되는데 직후 비교되는 글자의 쌍은 텍스트의 8번째 글자인 b와 패턴의 5번째 글자인 b이다.
이것은 이전 알고리즘에서 2,3번째 바깥쪽 루프와, 안쪽 루프의 첫 4단계를 건너뛴 것이다.
이것이 가능한 이유는 패턴의 반복성 때문에 바깥쪽 2개의 루프에는 답이 있을 수 없고, 4번째 루프에서는 앞의 4글자가 같음을 알고 있기 때문이다. 이 정보는 패턴을 이용해서 얻을 수 있다.

이 방법의 문제점은 설명서에 필요한 공간이 가능한 문자의 수 곱하기 패턴의 길이 정도로 길다는 점이다.
시간복잡도를 O(m+n)으로 낮추기 위해 다음과 같이 변형을 한다.
1. 왼쪽으로 가는 화살표는 하나만 두며
2. 위의 그림에서 가장 가까운 곳으로 가는 화살표의 하나 왼쪽으로 한다.
3. 왼쪽 화살표를 따르는 경우 텍스트의 현재 글자를 다시한번 읽는다.

이제, 매칭 과정의 시간 복잡도는 간단히 O(n)이라 하기 어렵다.
(텍스트 한 글자를 여러번 읽을 수 있다.)
오른쪽 화살표를 움직이는 것은 텍스트 상에서 보는 위치를 오른쪽으로 옮기는 것이다.
이 과정은 최대 n번 밖에 없다.
왼쪽 화살표를 따르는 것은 패턴이 텍스트 상에서 맞추어진 위치를 오른쪽으로 옮기는 것이다.
이 과정도 n번 이상 일어날 수 없다.
따라서 변형된 알고리즘의 매칭 과정은 O(n) 시간이 걸린다.
이것은 패턴 위를 입력된 텍스트가 뛰어다니는 것과 같습니다.

학부때 들었던 교수님의 명강의와 수업자료를 정리해 만들었는데 잘 이해가 되셨는지요?
손으로 그리면서 따라가 보시면 이해가 더 쉽습니다. 그리고 여러번 이것에 관해 생각해 보신다면 자연스럽게 개념정리가 되실꺼라 확신합니다.

출처 : http://blog.daum.net/autumn78/8068135